package com.practice.ajCollections010.map.hashmap;

import java.util.HashMap;
import java.util.Map;

/**
 * HashMap 扩容：
 *              1. 默认构造方法初始化的 HashMap 返回一个空 table，并且 threshold 为 0。默认容量 DEFAULT_INITIAL_CAPACITY 为 16，threshold 为 16 * 0.75 = 12；
 *              2. 指定初始容量的构造方法初始化 HashMap，threshold = threshold * DEFAULT_INITIAL_CAPACITY，比如：指定容量为 5 则 threshold 为 2^3 * 0.75 = 6；
 *              3. HashMap 不是第一次扩容。如果 HashMap 已经扩容过的话，那么每次 table 的容量以及 threshold 量为原有的两倍。
 *              4. 当 TREEIFY_THRESHOLD 的值大于 8 时，就会生成红黑树，红黑树的查找复杂度为 O(log n)
 */
public class Grow {

    //默认初始化容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //由列表散列转换为红黑树的阀值
    static final int TREEIFY_THRESHOLD = 8;
    //由红黑树转换为列表散列的阀值
    static final int UNTREEIFY_THRESHOLD = 6;
    //红黑树的最小容量
    static final int MIN_TREEIFY_CAPACITY = 64;
    //键值映射的总数量
    transient int size;
    //记录对HashMap进行结构修改的次数，用于迭代器快速失败机制
    transient int modCount;
    //下一个要调整大小的值
    int threshold;

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    public static void main(String[] args) {
        /**
         * 上边 tableSizeFor 上边是 HashMap 扩容机制，传入的容量是 10，其实初始化 HashMap 的容量时 0.75 *  16 = 12
         * 所以map存储 10 数据不会触发扩容
         * 如果传入容量参数为 13，则存储 13 个数据时会触发一次扩容
         */
        HashMap<String, String> map = new HashMap<>(10);
        map.put("hello", "world");
        System.out.println(map.size());
        System.out.println(tableSizeFor(MAXIMUM_CAPACITY));
        System.out.println(tableSizeFor(5));
    }
}
